/*
 *  test.h
 *  CarDemo
 *
 *  Created by huang kun on 8/11/10.
 *  Copyright 2010 UESTC. All rights reserved.
 *
 */

//Dijkstra算法求两点间的最短路径及其长度
#define INF 32767
#define MAX_VERTEX_NUM 20
typedef struct Arc{
	int adj;                     //权值
}AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct{
	int vex[MAX_VERTEX_NUM];    //顶点向量
	AdjMatrix arcs;            //邻接距阵
	int vexnum,arcnum;         //顶点个数，弧个数
}MGraph;
void InitMGraph(MGraph g){
	//初始化图
	int i,j;
	g.vexnum=12;g.arcnum=12;
	for(i=0;i<12;++i)
		g.vex[i]=i;
	for(i=0;i<12;++i)
		for(j=0;j<12;++j)
			g.arcs[i][j].adj=INF;
	g.arcs[0][1].adj=15;g.arcs[0][2].adj=4;g.arcs[0][3].adj=7;g.arcs[1][2].adj=7;g.arcs[1][4].adj=15;
	g.arcs[1][5].adj=12;g.arcs[2][4].adj=16;g.arcs[3][4].adj=8;g.arcs[3][8].adj=26;g.arcs[4][5].adj=20;
	g.arcs[4][6].adj=18;g.arcs[4][8].adj=30;g.arcs[5][9].adj=30;g.arcs[6][9].adj=16;g.arcs[6][7].adj=3;
	g.arcs[7][8].adj=7;g.arcs[8][9].adj=5;g.arcs[8][10].adj=15;g.arcs[9][11].adj=20;g.arcs[10][11].adj=9;	
	for(i=0;i<12;++i)
		for(j=i;j<12;++j)
			if(g.arcs[i][j].adj!=INF)
				g.arcs[j][i].adj=g.arcs[i][j].adj;//无向图的对称性
}
void ShortestPath_DIJ(MGraph g,int s,int t){
	//计算s点到t点的最短路径
	int d[12];
	bool p[12][12];
	bool final[12];
	int i,j,k,min,num;
	for(i=0;i<g.vexnum;++i){
		final[i]=false;
		d[i]=g.arcs[s][i].adj;
		for(j=0;j<g.vexnum;++j)
			p[i][j]=false;
		if(d[i]<INF){	p[i][s]=true;	p[i][i]=true;	}
	}
	d[s]=0;final[s]=true;
	for(k=1;k<g.vexnum;++k){
		min=INF;
		for(j=0;j<g.vexnum;++j)
			if(!final[j])
				if(d[j]<min){
					i=j;min=d[j];
				}
		final[i]=true;
		for(j=0;j<g.vexnum;++j)
			if(!final[j]&&(min+g.arcs[i][j].adj<d[j])){
				d[j]=min+g.arcs[i][j].adj;
				for(num=0;num<g.vexnum;++num)p[j][num]=p[i][num];
				p[j][j]=true;
			}
	}
	//cout<<"最短路径长度为："<<endl;
	//cout<<d[t]<<endl;
	//cout<<"最短路径为："<<endl;
	printf("最短路径长度为：%d\n",d[t]);
	printf("最短路径为：\n");
	
	for(i=0;i<g.vexnum;++i)
		if(p[t][i])printf("%d ",i);//cout<<i<<" ";
	//cout<<endl;
	printf("\n");
}
int test(){
	MGraph g;
	int s=0,t=9;
	//InitMGraph(g);
	//初始化图
	int i,j;
	g.vexnum=12;g.arcnum=12;
	for(i=0;i<12;++i)
		g.vex[i]=i;
	for(i=0;i<12;++i)
		for(j=0;j<12;++j)
			g.arcs[i][j].adj=INF;
//	g.arcs[0][1].adj=15;g.arcs[0][2].adj=4;g.arcs[0][3].adj=7;g.arcs[1][2].adj=7;g.arcs[1][4].adj=15;
//	g.arcs[1][5].adj=12;g.arcs[2][4].adj=16;g.arcs[3][4].adj=8;g.arcs[3][8].adj=26;g.arcs[4][5].adj=20;
//	g.arcs[4][6].adj=18;g.arcs[4][8].adj=30;g.arcs[5][9].adj=30;g.arcs[6][9].adj=16;g.arcs[6][7].adj=3;
//	g.arcs[7][8].adj=7;g.arcs[8][9].adj=30;g.arcs[8][10].adj=15;g.arcs[9][11].adj=20;g.arcs[10][11].adj=19;	
	
	g.arcs[0][1].adj=1;g.arcs[0][2].adj=1;g.arcs[0][3].adj=1;g.arcs[1][2].adj=1;g.arcs[1][4].adj=1;
	g.arcs[1][5].adj=1;g.arcs[2][4].adj=1;g.arcs[3][4].adj=1;g.arcs[3][8].adj=1;g.arcs[4][5].adj=1;
	g.arcs[4][6].adj=1;g.arcs[4][8].adj=1;g.arcs[5][9].adj=1;g.arcs[6][9].adj=1;g.arcs[6][7].adj=1;
	g.arcs[7][8].adj=1;g.arcs[8][9].adj=1;g.arcs[8][10].adj=1;g.arcs[9][11].adj=1;g.arcs[10][11].adj=1;	
	for(i=0;i<12;++i)
		for(j=i;j<12;++j)
			if(g.arcs[i][j].adj!=INF)
				g.arcs[j][i].adj=g.arcs[i][j].adj;//无向图的对称性
	
	

	//cout<<"求s到t的最短路径，请输入s,t的值"<<endl;
	//cin>>s>>t;
	if(s<0||s>11||t<0||t>11){printf("ERROR");return 0;}
	ShortestPath_DIJ(g,s,t);
	return 0;
}
